package hebClustering.clusteringAlgorithms;

import hebClustering.Cluster;
import hebClustering.ClusterSet;
import hebClustering.vectorSpace.IVector;
import hebClustering.vectorSpace.distances.IDistance;

import java.util.Collection;
import java.util.HashSet;
import java.util.Set;

/**
 * @author Ran Zvilik
 * Implementation of a newly devised clustering algorithm which is 
 * a variation of the K-Means Algorithm. It operates by initially doing the K-Means++ algorithm on the data
 * and then constantly taking the worst cluster in terms of SSE and performing K-Means++ on it if it's SSE isn't epsilon
 * bound. During the entire procedure  singleton clusters are removed and put aside.
 * When epsilon bound is finally reached for all clusters, the algorithm iterates over the vectors
 * which were left out and tries to find a cluster C such that it's SSE after the vector is added
 * will be bounded by delta.
 * 
 * IMPORTANT NOTE: Not all the initial vectors are included in the final clustering
 * since the left out vectors which the algorithm can't find a delta bound cluster for them, won't
 * be included.*/

public class EpsilonDeltaMeansClustering extends KMeansClustering {

	private double epsilon;
	private double delta;
	
	private Set<IVector> singletons = new HashSet<IVector>();
	private KMeansPPClustering kmeansPP = new KMeansPPClustering(K,I,distance);

	public EpsilonDeltaMeansClustering(double epsilon,double delta,IDistance distance){
		super(10,60,distance);
		this.delta = delta;
		this.epsilon = epsilon;
	}

	@Override
	public ClusterSet cluster(Collection<IVector> dataSet) {
		/*Initial Clustering*/
		ClusterSet clusterSet = kmeansPP.cluster(dataSet);
		singletons.addAll(pullSingletons(clusterSet));
		
		epsilonCut(clusterSet);
		
		deltaAssign(singletons,clusterSet);
		
		return clusterSet;
	}

	private void deltaAssign(Collection<IVector> singletons,ClusterSet clusterSet) {
		int num = 0;
		
		for(IVector v : singletons) {
			Cluster cluster = getNearesetCluster(v,clusterSet);
			double sseBefore = cluster.getSSE();
			cluster.add(v);
			double sseAfter = cluster.getSSE();
			
			if(sseAfter > sseBefore*(1+delta)){
				cluster.remove(v);
			}
			else num++;
		}
		
	}

	private void epsilonCut(ClusterSet clusterSet) {
		Cluster worstCluster = getWorstCluster(clusterSet);
		while(! (worstCluster.getSSE()<epsilon)){

			clusterSet.remove(worstCluster);
			kmeansPP.setK( (int) Math.sqrt(worstCluster.size()) );
			ClusterSet clusterCut = kmeansPP.cluster(worstCluster);
			singletons.addAll(pullSingletons(clusterCut));
			clusterSet.addAll(clusterCut);
			
			worstCluster = getWorstCluster(clusterSet);
		}
	}

	private Cluster getWorstCluster(ClusterSet clusterSet) {
		double maxSSE = Double.MIN_VALUE;
		Cluster worst = null; 
		
		for(Cluster cluster : clusterSet){
			double currentSSE = cluster.getSSE();
			if(maxSSE<currentSSE){
				maxSSE = currentSSE;
				worst = cluster;
			}
		}
		
		return worst;
	}

	private Set<IVector> pullSingletons(ClusterSet clusterSet) {
		Set<IVector> vectors = new HashSet<IVector>();
		Set<Cluster> singletons = new HashSet<Cluster>();
		
		for(Cluster cluster : clusterSet){
			if(cluster.size()==1){
				vectors.add(cluster.getRandomVector());
				singletons.add(cluster);
			}
		}
		
		clusterSet.removeAll(singletons);
		
		return vectors;
	}
	
	public String toString(){
		return "EDM";
	}

}
